package com.tree.leetcode.array;

import cn.hutool.json.JSONUtil;
import com.tree.array.ArrayList;

import java.util.List;

/**
 * @ClassName com.tree.leetcode.array
 * Description: 287. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2
示例 2：

输入：nums = [3,1,3,4,2]
输出：3
 * @Author frankzsliu
 * @Date 2024/2/3 22:58
 * @Version 1.0
 */
public class FindDuplicate_287 {
    public static void main(String[] args) {
        int[] nums = {1,3,4,2,2};
        System.out.println(findDuplicate2(nums));
    }

    public static int findDuplicate(int[] nums) {
//        return  findDuplicateBySlowFasterPointer(nums);
        return  findDuplicateBySlowFasterPointer(nums);

    }

    public static int findDuplicate2(int[] nums){
        int n = nums.length;
        for(int i =0 ;i< n; i++){
            //如果当前位置i和当前位置值nums[i]不相等
            while (nums[i] != nums[nums[i]]) {
                //交换前发现i位置的值nums[i]和所在值所对应的位置nums[nums[i]]， 那就代表找到了
//                if (nums[i] == nums[nums[i]]) {
//                    return nums[i];
//                }
                //交换： i = nums[i] , 即nums[i] = nums[nums[i]]
                int tmp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = tmp;
            }
        }

        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            if (nums[i]  != i) {
                ans.add(nums[i]);
            }
        }
        System.out.println(JSONUtil.toJsonStr(ans));
        return -1;
    }


    /**
     * 方法1 ： 快慢指针, 原理参考： https://www.bilibili.com/video/BV1aV411q7DM/?spm_id_from=333.337.search-card.all.click&vd_source=7e2be45040616926464653326437b06f
     * 参考：141. 环形链表 https://leetcode.cn/problems/linked-list-cycle/description/
     *  1. n 个节点的值：1 , 2 , ⋯, n ；
     *  2. 对于每个节点 i ，其 next 引用指向节点 nums[i] 。
     *
     * @param nums
     * @return
     */
    public static int findDuplicateBySlowFasterPointer(int[] nums) {
         int slow =0 ; int fast = 0;
        // 第一次相遇
         do{
             slow = next(nums, slow);
             //fast节点取 当前slow的值的下一个节点
             fast = next(nums, next(nums,fast));
         } while (slow != fast);
         slow = 0;
        // 第二次相遇
         while (slow != fast){
             slow = next(nums, slow);
             fast = next(nums, fast);
         }
         return slow;

    }

    private static int next(int[] nums, int index) {
        return nums[index];
    }



}
